// [2316]统计无向图中无法互相到达点对数
struct Solution;

//leetcode submit region begin(Prohibit modification and deletion)
impl Solution {
    pub fn count_pairs(n: i32, edges: Vec<Vec<i32>>) -> i64 {
        let mut ans = 0;
        let n = n as usize;
        let mut g = vec![vec![]; n];
        for edge in edges {
            let x = edge[0] as usize;
            let y = edge[1] as usize;
            g[x].push(y);
            g[y].push(x);
        }
        let mut total = 0;
        let mut visited = vec![false; n];
        for i in 0..n {
            if !visited[i] {
                let size = Self::dfs(i, &g, &mut visited);
                ans += size as i64 * total as i64;
                total += size;
            }
        }
        ans
    }

    fn dfs(i: usize, g: &Vec<Vec<usize>>, visited: &mut Vec<bool>) -> i32 {
        visited[i] = true;
        let mut size = 1;
        for &y in &g[i] {
            if !visited[y] {
                size += Self::dfs(y, g, visited);
            }
        }
        size
    }
}
//leetcode submit region end(Prohibit modification and deletion)


#[test]
fn main() {
    let edges = vec![
        vec![0,1],
        vec![0,2],
        vec![1,2],
    ];
    assert_eq!(Solution::count_pairs(3, edges), 0);

    let edges = vec![
        vec![0,2],
        vec![0,5],
        vec![2,4],
        vec![1,6],
        vec![5,4],
    ];
    assert_eq!(Solution::count_pairs(7, edges), 14);
}